package site.wanjiahao.graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 对于图来说，存在两种数据
 *      边
 *      顶点
 */
public interface Graph<V, E> {

    int edgeSize();

    int vertexSize();

    void addEdge(V from, V to);

    void addEdge(V from, V to, E weight);

    void addVertex(V value);

    void removeEdge(V from, V to);

    void removeVertex(V value);

    void bfs(V begin, Consumer consumer);

    void dfs(V begin, Consumer consumer);

    List<V> topologicSort();

    Set<EdgeInfo<V, E>> mst();

    Map<V, PathInfo<V, E>> shortestPath(V begin);

    Map<V, Map<V, PathInfo<V, E>>> shortestPath();

    abstract class Consumer<V> {
        boolean isStop = false;

        protected abstract boolean accept(V v);
    }

    // 权重比较器
    interface WeightManager<E> {

        int compare(E e1, E e2);

        E zero();

        E max();

        E add(E e1, E e2);

    }

    // 定义路径信息
    class PathInfo<V, E> {
        // 路径权重信息
        private E weight;

        // 路径边信息，需要是有顺序的
        private List<EdgeInfo<V, E>> edgeInfos;

        public PathInfo(E weight) {
            this.weight = weight;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public List<EdgeInfo<V, E>> getEdgeInfos() {
            if (edgeInfos == null) {
                edgeInfos = new LinkedList<>();
            }
            return edgeInfos;
        }

        public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) {
            this.edgeInfos = edgeInfos;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("PathInfo{");
            sb.append("weight=").append(weight);
            sb.append(", edgeInfos=").append(edgeInfos);
            sb.append('}');
            return sb.toString();
        }
    }

    // 定义最小生成树的边实体对象
    class EdgeInfo<V, E> {

        private V from;

        private V to;

        private E weight;


        public EdgeInfo(V from, V to, E weight) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("EdgeInfo{");
            sb.append("from=").append(from);
            sb.append(", to=").append(to);
            sb.append(", weight=").append(weight);
            sb.append('}');
            return sb.toString();
        }
    }
}
